package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/** @author haoyang.shi */
public class GetNumberOfK {

  @Test
  public void test() {
    System.out.println(GetNumberOfK(new int[] {1, 2, 6, 6, 6, 6, 6, 7}, 6));
    System.out.println(GetNumberOfK(new int[] {3, 3, 3, 3, 4, 5}, 3));
  }

  public int GetNumberOfK(int[] array, int k) {
    if (array == null || array.length == 0) {
      return 0;
    }

    // 二分查找
    int start = 0, end = array.length - 1;
    int t = -1;
    while (start < end) {
      int mid = (start + end) / 2;
      if (array[mid] == k) {
        t = mid;
        break;
      } else if (array[mid] > k) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }

    if (array[start] == k) {
      t = start;
    }

    if (t == -1) {
      return 0;
    }

    // 左侧
    int sum = 0;
    int a = t;
    while (a >= 0 && array[a] == k) {
      sum++;
      a--;
    }

    // 右侧
    a = t + 1;
    while (a < array.length && array[a] == k) {
      sum++;
      a++;
    }

    return sum;
  }
}
